Přeskočit na obsah

Master theorem

Z Wikipedie, otevřené encyklopedie

Master theorem (také Kuchařková věta nebo Mistrovská metoda) je speciální případ Akra-Bazzi theoremu, poskytuje při analýze složitosti algoritmů kuchařkové řešení asymptotické složitosti pro často používané rekurentní vztahy. Byl popularizován knihou Introduction to Algorithms napsanou Cormenem, Leisersonem, Rivestem a Steinem, kde je uveden a dokázán v sekcích 4.3 a 4.4.

Obecná forma

[editovat | editovat zdroj]

Master theorem řeší rekurentní vztahy ve tvaru:

, kde

Při analýze rekurzivních algoritmů mají konstanty a funkce následující význam:

  • je velikost problému.
  • je počet podproblémů v rekurzi.
  • je velikost každého z podproblémů. Předpokládá se, že podproblémy jsou víceméně stejně velké.
  • je cena práce mimo rekurzivní volání, zahrnující rozdělení problému na podproblémy a sloučení výsledků podproblémů.

Je možné zjistit asymptotickou složitost v následujících třech případech:

Případ 1

[editovat | editovat zdroj]

Obecný tvar

[editovat | editovat zdroj]

Pokud platí, že pro nějaké

tak:

Z výše uvedené rovnice vidíme, že hodnoty jsou:

, , ,

Nyní musíme zkontrolovat, zda platí:

Po dosazení hodnot dostaneme:

Pokud zvolíme = 1, dostaneme:

Protože rovnost platí, první případ master theoremu lze použít na danou rekurentní rovnost, čímž dostaneme:

Po dosazení hodnot:

Tedy pro daný rekurentní vztah T(n) je v Θ(n³).

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je , za předpokladu .)

Případ 2

[editovat | editovat zdroj]

Obecný tvar

[editovat | editovat zdroj]

Pokud platí:

tak:

Z výše uvedené rovnice vidíme, že hodnoty jsou:

, , , ,

Nyní ověříme, že následující rovnost platí (v tomto případě k=0):

Po dosazení dostaneme:

Protože rovnost platí, druhý případ master theoremu lze aplikovat, čímž dostáváme:

Po dosazení:

Tedy pro daný rekurentní vztah T(n) je v Θ(n log n).

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je , za předpokladu .)

Případ 3

[editovat | editovat zdroj]

Obecný tvar

[editovat | editovat zdroj]

Pokud platí:

pro nějaké

a také platí:

pro nějaké a dostatečně velké n

tak:

Z výše uvedené rovnice vidíme, že hodnoty jsou:

, , ,

Nyní ověříme, že následující rovnost platí:

Pokud dosadíme hodnoty a zvolíme = 1, dostaneme:

Protože rovnost platí, ověříme druhou podmínku, konkrétně, že:

Opět dosadíme hodnoty:

Pokud zvolíme , tak platí:

Tedy:

Opět dosadíme hodnoty a dostaneme:

Tedy pro daný rekurentní vztah T(n) je v Θ(n²), což odpovídá f (n) v původním vzorci.

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je , za předpokladu .)

Nepřípustné rovnice

[editovat | editovat zdroj]

Následující rovnice nelze vyřešit pomocí master theoremu:[1]

To protože a (2n) není konstanta.

Mezi f(n) a je nepolynomiální rozdíl.

Nelze mít méně, než jeden podproblém (a<1).

f(n) není kladné.

Případ 3, ale porušení regularity.

V tomto článku byl použit překlad textu z článku Master theorem na anglické Wikipedii.

  1. Archivovaná kopie. www.cag.lcs.mit.edu [online]. [cit. 2009-04-24]. Dostupné v archivu pořízeném dne 2009-02-05. 

Literatura

[editovat | editovat zdroj]